//https://leetcode.cn/problems/sliding-window-maximum/
package codeRandomThoughts.Test239滑动窗口最大值;

import java.util.Deque;
import java.util.LinkedList;

//单调队列
//规定队头元素最大
//队尾元素最小
class MyQueue4 {
    //双边队列
    Deque<Integer> deque;

    public MyQueue4() {
        deque = new LinkedList<>();
    }

    //获取最大值
    public int getFront() {
        return deque.getFirst();
    }

    //往单调队列里添加值
    public void push(int val) {
        while (!deque.isEmpty() && deque.getLast() < val) {
            deque.pollLast();
        }
        deque.offerLast(val);
    }

    public void pop(int val) {
        if (val == deque.getFirst()) {
            deque.removeFirst();
        }
    }
}

public class Solution4 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        MyQueue4 queue = new MyQueue4();
        //滑动窗口左右边界
        int left = 0;
        int right = 0;

        //初始化滑动窗口
        while (right <= k - 1) {
            queue.push(nums[right]);
            right++;
        }
        right--;//上面多减了一次,补回来
        res[0] = queue.getFront();

        //窗口开始滑动
        while (right < nums.length - 1) {
            //left右移
            queue.pop(nums[left]);
            left++;
            //right右移
            right++;
            queue.push(nums[right]);

            //记录当前滑动窗口的最大值
            res[left] = queue.getFront();
        }

        return res;
    }
}